/**
 * 
 */
package leetCode;

/**
 * @author zhong
 *
 */
public class GlobalandLocalInversions {
	public boolean isIdealPermutation(int[] A) {
		int localCount = 0;
		for (int i = 0; i < A.length - 1; i++) {
			if (A[i] > A[i + 1]) {
				localCount++;
			}
		}
		int[] tmp = new int[A.length];
		int globalCount = getCount(A, tmp, 0, A.length - 1);
		System.out.println(localCount + " " + globalCount);
		return localCount == globalCount;
	}

	private int getCount(int[] a, int[] tmp, int start, int end) {
		if (start >= end)
			return 0;

		int mid = (start + end) >> 1;
		int c = getCount(a, tmp, start, mid) + getCount(a, tmp, mid + 1, end);
		c += merge(a, tmp, start, mid, end);
		return c;
	}

	private int merge(int[] a, int[] tmp, int start, int mid, int end) {
		int res = 0;
		int i = start, j = mid + 1, k = start;
		while (i <= mid && j <= end) {
			if (a[i] <= a[j]) {
				tmp[k++] = a[i++];
			} else {
				tmp[k++] = a[j++];
				res += mid - i + 1;
			}
		}
		while (i <= mid) {
			tmp[k++] = a[i++];
		}
		while (j <= end) {
			tmp[k++] = a[j++];
		}
		for (int k2 = start; k2 <= end; k2++) {
			a[k2] = tmp[k2];
		}
		return res;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] A = { 1, 2, 0 };
		System.out.println(new GlobalandLocalInversions().isIdealPermutation(A));
	}

}
